package com.duoduo.深度广度优先;

import com.duoduo.TreeNode;

import java.util.LinkedList;
import java.util.List;

/**
 * @program: algorithm
 * @description: 二叉树中和为某一值的路径 34
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 * 叶子节点 是指没有子节点的节点
 * @author: chaidl  ！
 * @create: 2022-03-02 16:00
 */
public class 二叉树中和为某一值的路径 {
    LinkedList<List<Integer>> result = new LinkedList<>();
    LinkedList<Integer> list = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root, target);
        return result;

    }
    //深度优先搜索
    private void dfs(TreeNode root, int target) {
        if (root == null) {
            return;
        }
        //先把当前数据放入list
        list.add(root.val);
        target = target - root.val;
        if (target == 0 && root.left == null && root.right == null) {
            result.add(new LinkedList<>(list));
        }
        dfs(root.left, target);
        dfs(root.right, target);
        list.removeLast();
    }
}
